 1.贪心之案例三
   
   0-1 背包问题
   有n件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑥i、价值是 𝑤i
      在保证总重量不超过 W 的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？
      注意：每个物品只有 1 件,也就是每个物品只能选择 0 件或者 1 件，因此这类问题也被称为 0-1 背包问题
   1、 价值主导：优先选择价值最高的物品放进背包 
   2、 重量主导：优先选择重量最轻的物品放进背包 
   3、 价值密度主导：优先选择价值密度最高的物品放进背包（价值密度 = 价值 ÷ 重量）
   以下是物品列表：
   物品序号   1    2    3   4   5    6   7
   重量       35   30   60  50  40   10  25
   价值       10   40   30  50  35   40  30
   价值密度   0.29 1.33 0.5 1.0 0.88 4.0 1.2 
   
   假设背包总载重量是150，将哪几件物品装入背包，可以使得背包的总价值最大？
   代码实现
package com.lg.packsack;

public class Item {
    //重量，价值，价值密度
    private int weight;
    private int value;
    private double valueDen;

    public Item() {
    }

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.valueDen = value/weight;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public double getValueDen() {
        return valueDen;
    }

    public void setValueDen(double valueDen) {
        this.valueDen = valueDen;
    }

    @Override
    public String toString() {
        return "Item{" +
                "weight=" + weight +
                ", value=" + value +
                ", valueDen=" + valueDen +
                '}';
    }
}


package com.lg.packsack;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 假设背包总载重量是150，将哪几件物品装入背包，可以使得背包的总价值最大？
 */
public class PackSack {
    public static void main(String[] args) {
        //准备货物
        Item[] items ={
                new Item(35, 10),
                new Item(30, 40),
                new Item(60, 30),
                new Item(50, 50),
                new Item(40, 35),
                new Item(10, 40),
                new Item(25, 30),
        };
        /**
         * 1、价值主导：优先选择价值最高的物品放进背包
         * 2、重量主导：优先选择重量最轻的物品放进背包
         * 3、价值密度主导：优先选择价值密度最高的物品放进背包（价值密度 = 价值 ÷ 重量）
         */

        //价值主导
        System.out.println("价值主导的选择结果：");
        packSackMethod(items, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o2.getValue()-o1.getValue();
            }
        });

        //重量主导
        System.out.println("重量主导的选择结果：");
        packSackMethod(items, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o1.getWeight()-o2.getWeight();
            }
        });

        //密度主导
        System.out.println("密度主导的选择结果：");
        packSackMethod(items, new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return Double.compare(o2.getValueDen(), o1.getValueDen());
            }
        });
    }
    // 贪心策略0-1背包 价值最大化
    static void packSackMethod(Item[] items, Comparator<Item> comp){
        //按照要求对货物进行排序
        Arrays.sort(items, comp);
        //遍历数组，取出策略要求价值最大的物品
        int capacity=150;
        int itemNum=0;
        //已装载的重量
        int weigtht=0;
        //初始总价值
        int value=0;
        for (int i = 0; i < items.length; i++) {
            int newWeight =weigtht+items[i].getWeight();
            if (newWeight <=capacity){
                itemNum++;
                value+=items[i].getValue();
                weigtht=newWeight;
                //打印物品
                System.out.println(items[i].toString());
            }
        }
        System.out.println("共选择了" + itemNum + "件物品！！！");
        System.out.println("总价值" +value);
        System.out.println("总重量" + weigtht);
        System.out.println("-----------------------------------");
    }
}
   